package com.atwy.graph.undirectedgraph;

/**
 * @Author: 小王子火
 * @Date: 2022/3/16
 * 双色问题，二分图
 * 能够用两种颜色将图的所有顶点着色，使得任意一条边的两个端点的颜色都不相同
 */
public class TwoColor {
    /**
     * 记录某个顶点是否被访问到
     */
    private boolean[] marked;
    /**
     * 标记每个顶点的颜色，true为白色，false为黑色
     */
    private boolean[] color;
    /**
     * 该图是否是二分图,默认是
     */
    private boolean isTwoColorable = true;

    public TwoColor(IGraph graph) {
        marked = new boolean[graph.V()];
        color = new boolean[graph.V()];
        for (int s = 0; s < graph.V(); s++) {
            if(!marked[s]){

                dfs(graph,s);
            }
        }
    }

    private void dfs(IGraph graph, int s) {
        marked[s] = true;
        for (int w : graph.adj(s)) {
            if(!marked[w]){
                // 顶点与邻接点是不同颜色
                color[w] = !color[s];
                dfs(graph,w);
            }else if (color[w] == color[s]){
                isTwoColorable = false;
            }
        }

    }

    public boolean isTwoColorable(){
        return isTwoColorable;
    }
}
